[Python] 二つのListのIntersection（交差）を高速化する

[Salesforce] Listのintersection（積集合）の高速化 の　Python版です。

数万件の要素があるような二つのListでIntersectionを以下のようにループのループで取ってしまうと O(n^2) になるため、AWS Lambdaの実行時間制限15分に抵触してしまったりしてうまくありません。

list1 = [1, 2, ... , 50000]
list2 = [25001, 25002, ... , 75000]

results = []
for e1 in list1:
    for e2 in list2:
        if e1 == e2:
            results.append(e1)

そこで、片方のListをSet化することで計算量を O(n1 + n2)にできます。

list1 = [1, 2, ... , 50000]
list2 = [25001, 25002, ... , 75000]

set2 = set(list2)  # O(n2)
results = []
for n in list1:  # O(n1)
    if n in set2:  # O(1)
        results.append(n)  # O(1)